package leetcode.code528;


public class Solution extends Solution528 {

	private int[] w;
	private int len;

	public Solution(int[] w) {
		this.w = w;
		this.len = w.length;
		this.init();
	}

	private void init() {
		for (int i = 1; i < len; i++) {
			w[i] = w[i] + w[i - 1];
		}
	}

	@Override
	public int pickIndex() {
		int rn = (int) (Math.random() * w[len-1]) + 1;
		int l = 0;
		int r = len - 1;
		while (l < r) {
			int m = ((r - l) >> 1) + l;
			if (w[m] < rn) {
				l = m + 1;
			} else {
				r = m;
			}
		}
		return r;
	}

	public static void main(String[] args) {
		Solution so = new Solution(new int[] { 3, 14, 1, 7 });
		for (int i = 0; i < 100; i++) {
			int result = so.pickIndex();
			System.out.println(result);
		}
	}

}
